public class Solution123 {
    public int maxProfit(int[] prices) {
        if (prices.length==1){
            return 0;
        }
        int[] f1=new int[prices.length];
        f1[0]=-prices[0];
        for (int i=1;i<prices.length;i++){
            f1[i]=Math.max(f1[i-1],-prices[i]);
        }
        int[] f2=new int[prices.length];
        f2[0]=0;
        for (int i=1;i<prices.length;i++){
            f2[i]=Math.max(f2[i-1],f1[i-1]+prices[i]);
        }
        int[] f3=new int[prices.length];
        f3[1]=-prices[1];
        for (int i=2;i<prices.length;i++){
            f3[i]=Math.max(f3[i-1],f2[i-1]-prices[i]);
        }
        int[] f4=new int[prices.length];
        f4[1]=0;
        for (int i=2;i<prices.length;i++){
            f4[i]=Math.max(f4[i-1],f3[i-1]+prices[i]);
        }
        return Math.max(0,Math.max(f2[prices.length-1],f4[prices.length-1]));
    }

    public static void main(String[] args) {
        System.out.println(new Solution123().maxProfit(new int[]{3,3,5,0,0,3,1,4}));
    }

}
